/*
 * @Author: HuanXX shy2757539057@163.com
 * @Date: 2024-10-01 18:26:49
 * @LastEditors: HuanXX
 * @LastEditTime: 2024-10-01 12:19:29
 * @Description: file content
 */
package dp.lcs;
public class Main {
    public static void main(String[] args) {
        String a = "ABCBDAB";
        String b = "BDCABA";
        int[][] maxvalue = new int[a.length() + 1][b.length() + 1];
        int[][] subquest = new int[a.length() + 1][b.length() + 1];
        lcsLength(a.length(), b.length(), a, b, maxvalue, subquest);
        lcs(a.length(), b.length(), a, subquest);
    }

    public static void lcsLength(int lena, int lenb, String a, String b, int[][] maxvalue, int[][] subquest) {
        for (int i = 0; i <= lena; i++) {
            maxvalue[i][0] = 0;
        }
        for (int i = 0; i <= lenb; i++) {
            maxvalue[0][i] = 0;
        }
        for (int i = 1; i <= lena; i++) {
            for (int j = 1; j <= lenb; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    maxvalue[i][j] = maxvalue[i - 1][j - 1] + 1;
                    subquest[i][j] = 1;
                } else if (maxvalue[i - 1][j] >= maxvalue[i][j - 1]) {
                    maxvalue[i][j] = maxvalue[i - 1][j];
                    subquest[i][j] = 2;
                } else {
                    maxvalue[i][j] = maxvalue[i][j - 1];
                    subquest[i][j] = 3;
                }
            }
        }
    }

    public static void lcs(int enda, int endb, String a, int[][] subquest) {
        if (enda == 0 || endb == 0) {
            return;
        }
        switch (subquest[enda][endb]) {
            case 1 -> {
                lcs(enda - 1, endb - 1, a, subquest);
                System.out.printf("%c", a.charAt(enda - 1));
            }
            case 2 -> lcs(enda - 1, endb, a, subquest);
            default -> lcs(enda, endb - 1, a, subquest);
        }
    }
}
